package com.zjj.algorithm.learning.leetcode.linkedlist;

/**
 * 86. 分隔链表 中等
 *
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 *
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 *
 * 输入：head = [1,4,3,2,5,2], x = 3
 * 输出：[1,2,2,4,3,5]
 * 示例 2：
 *
 * 输入：head = [2,1], x = 2
 * 输出：[1,2]
 *
 * @author zjj_admin
 * @date 2022/11/10 15:14
 */
public class PartitionList {

    public static void main(String[] args) {

        ListNode node1 = new ListNode(3, null);
        ListNode node2 = new ListNode(0, node1);
        ListNode node3 = new ListNode(4, node2);
        ListNode node4 = new ListNode(1, node3);
        ListNode node5 = new ListNode(3, node4);
        ListNode node6 = new ListNode(1, node5);
        ListNode node7 = new ListNode(4, node6);
        ListNode node8 = new ListNode(0, node7);
        ListNode node9 = new ListNode(2, node8);

        partition(node9,4);
        System.out.println("node7 = " + node7);

    }

    /**
     * 此方法为借鉴别人的
     * 借助两个链表
     * @param head
     * @param x
     * @return
     */
    public ListNode partition1(ListNode head, int x) {
        ListNode dummyHead1 = new ListNode(0);
        ListNode dummyHead2 = new ListNode(0);
        ListNode node1 = dummyHead1;
        ListNode node2 = dummyHead2;
        while (head != null) {
            if (head.val < x) {
                node1.next = head;
                head = head.next;
                node1 = node1.next;
                node1.next = null;
            } else {
                node2.next = head;
                head = head.next;
                node2 = node2.next;
                node2.next = null;
            }
        }
        node1.next = dummyHead2.next;
        return dummyHead1.next;
    }

    public static ListNode partition(ListNode head, int x) {
        ListNode curr = head;
        ListNode currPre = new ListNode();
        currPre.next = curr;
        ListNode focus = head;
        ListNode focusPre = new ListNode();
        focusPre.next = focus;
        boolean pass = false;
        ListNode temp;
        while (curr != null){
            if( !pass ){
                if(curr.val >= x){
                    focus = curr;
                    focusPre = curr != head ? focusPre.next : focusPre;
                    pass = true;
                }
            }
            if(pass && curr.val < x){
                currPre.next = currPre.next.next;
                if(focus != head){
                    focusPre.next = curr;
                    focusPre = focusPre.next;
                    focusPre.next = focus;
                    curr = currPre.next;
                }else {
                    focusPre.next = curr;
                    head = curr;
                    focusPre = focusPre.next;
                    focusPre.next = focus;
                    curr = currPre.next;
                }
            }else {
                curr = curr.next;
                currPre = currPre.next;
            }
        }
        return head;
    }
}
